{
  "metadata": {
    "language_info": {
      "codemirror_mode": {
        "name": "python",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8"
    },
    "kernelspec": {
      "name": "python",
      "display_name": "Pyolite",
      "language": "python"
    },
    "colab": {
      "name": "5.ipynb",
      "provenance": [],
      "collapsed_sections": []
    }
  },
  "nbformat_minor": 0,
  "nbformat": 4,
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "线性和循环卷积"
      ],
      "metadata": {
        "id": "SRkGWJqfZbpN"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "此示例说明如何建立线性卷积和循环卷积之间的等效关系。\n",
        "\n",
        "线性卷积和循环卷积是本质不同的运算。然而，在某些条件下，线性卷积和循环卷积是等效的。建立这种等效关系具有重要意义。对于两个向量x和y，循环卷积等于二者的离散傅里叶变换(DFT)之积的逆DFT变换。了解线性卷积和循环卷积等效的条件，可让您使用DFT来高效地计算线性卷积。\n",
        "\n",
        "包含N个点的向量x和包含L个点的向量y的线性卷积长度为N+L-1。\n",
        "\n",
        "为了使x和y的循环卷积与之等效，在进行DFT之前，必须用零填充向量，使长度至少为N+L-1。对DFT的积求逆后，只保留前N+L-1个元素。\n",
        "\n",
        "创建两个向量x和y，并计算两个向量的线性卷积。"
      ],
      "metadata": {
        "id": "m354aV5ZZ1tW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "# from numpy.fft import fft, ifft\n",
        "from scipy.fft import fft, ifft\n",
        "from matplotlib import pyplot as plt"
      ],
      "metadata": {
        "trusted": true,
        "id": "094mgdc9ZbpR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "x = np.array([2, 1, 2, 1])\n",
        "y = np.array([1, 2, 3])"
      ],
      "metadata": {
        "trusted": true,
        "id": "GSM9RiXTZbpS"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "输出长度为 4+3-1。\n",
        "\n",
        "用 0 填充两个向量，使长度为 4+3-1。求出两个向量的 DFT，将其相乘，并求乘积的逆 DFT。"
      ],
      "metadata": {
        "id": "mTo7o3PvaRq3"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "clin = np.convolve(x,y)\n",
        "N = len(x) + len(y) -1\n",
        "num = np.arange(1, N+1, 1)\n",
        "print(num)\n",
        "print(clin)"
      ],
      "metadata": {
        "trusted": true,
        "id": "OL94l0ZhZbpT",
        "outputId": "39de462b-b1d0-4835-bf42-6f9c3dbcee0b"
      },
      "execution_count": null,
      "outputs": [
        {
          "name": "stdout",
          "text": "[1 2 3 4 5 6]\n[ 2  5 10  8  8  3]\n",
          "output_type": "stream"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "xzeropad = np.zeros(N - len(x))\n",
        "yzeropad = np.zeros(N - len(y))\n",
        "xpad = np.concatenate([x, xzeropad])\n",
        "ypad = np.concatenate([y, yzeropad])\n",
        "print(xpad)\n",
        "print(ypad)"
      ],
      "metadata": {
        "trusted": true,
        "id": "1pYKs6C3ZbpU",
        "outputId": "df296e03-16e2-4743-f7ea-264f3e9041f6"
      },
      "execution_count": null,
      "outputs": [
        {
          "name": "stdout",
          "text": "[2. 1. 2. 1. 0. 0.]\n[1. 2. 3. 0. 0. 0.]\n",
          "output_type": "stream"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "ccirc = ifft(fft(xpad)*fft(ypad))\n",
        "print(ccirc)"
      ],
      "metadata": {
        "trusted": true,
        "id": "nNhQ3TT3ZbpU",
        "outputId": "3f71a55f-65c8-4d92-8e5a-671266ad77dd"
      },
      "execution_count": null,
      "outputs": [
        {
          "name": "stdout",
          "text": "[ 2.+0.j  5.+0.j 10.+0.j  8.+0.j  8.-0.j  3.+0.j]\n",
          "output_type": "stream"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "将向量填充到长度为12，并使用DFT之积的逆DFT求得循环卷积。仅保留前4+3-1个元素，以产生与线性卷积等效的结果。"
      ],
      "metadata": {
        "id": "JeXvdXpwaqzy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "xzeropads = np.zeros(12 - len(x))\n",
        "yzeropads = np.zeros(12 - len(y))\n",
        "xpads = np.concatenate([x, xzeropad])\n",
        "ypads = np.concatenate([y, yzeropad])\n",
        "\n",
        "ccircs = ifft(fft(xpad)*fft(ypad))\n",
        "ccircs = ccircs[0:N]"
      ],
      "metadata": {
        "trusted": true,
        "id": "6cGqmXLaZbpV"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "plt.subplot(311)\n",
        "plt.stem(num, clin)\n",
        "plt.title('Linear Convolution of x and y')\n",
        "\n",
        "plt.subplot(312)\n",
        "plt.stem(num, ccirc)\n",
        "plt.title('Circular Convolution of x and y')\n",
        "\n",
        "plt.subplot(313)\n",
        "plt.stem(num, ccircs)\n",
        "plt.title('Circular Convolution of x and y')\n",
        "\n",
        "plt.show()"
      ],
      "metadata": {
        "trusted": true,
        "id": "mC7LY2VlZbpW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "填零后的向量xpad和ypad的循环卷积等效于x和y的线性卷积。保留ccirc的所有元素，因为输出长度为4+3-1。\n",
        "\n",
        "绘制线性卷积的输出和DFT之积的逆，以显示二者等效。"
      ],
      "metadata": {
        "id": "IOBM2P1eacaa"
      }
    }
  ]
}